﻿//1124. 表现良好的最长时间段
//给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
//我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
//所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
//请你返回「表现良好时间段」的最大长度。



class Solution {
public:
    int longestWPI(vector<int>& hours)
    {
        int n = hours.size();
        stack<int> sta;
        int ans = 0;
        //前缀和
        for (int i = 0; i < n; i++)
        {
            hours[i] = hours[i] > 8 ? 1 : -1;
        }
        vector<int> prev(n + 1, 0);
        prev[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            prev[i] = hours[i - 1] + prev[i - 1];
        }
        //s[i]<s[j] && i<j 使 i-j 最大
        sta.push(0);
        for (int i = 1; i <= n; i++)
        {
            if (prev[i] < prev[sta.top()])
                sta.push(i);
        }
        for (int i = n; i; i--)
        {
            while (!sta.empty() && prev[i] > prev[sta.top()])
            {
                ans = max(ans, i - sta.top());
                sta.pop();
            }
        }
        return ans;
    }
};